
class Operation:
    ADD = 0
    MOD = 1
    DEL = 2

    def __init__(self, node, type, pair, dst, path=None):
        self.node = node
        self.type = type
        self.pair = pair
        self.dst = dst
        self.path = path
        self.timeout = 0.2 if type == self.ADD or type == self.MOD else 0.1

    def eq(self,other):
        assert isinstance(other, Operation)
        return self.node==other.node and self.type==other.type and self.pair==other.pair and self.dst==other.dst

    def __str__(self):
        return "node=%d, type=%d, pair=%s, dst=%s, path=%s"%(self.node,self.type,self.pair,self.dst,self.path)


class DepNode:
    INIT = 0
    EXECED = 1
    WAIT = 2
    def __init__(self,op):
        assert isinstance(op,Operation)
        self.op = op
        self.acquire = []
        self.release = []
        self.status = DepNode.INIT


class DepGraph:
    def __init__(self):
        self.nodes = None


    @classmethod
    def pair_construct(cls, pair, node_path1, node_path2):
        """
        :param pair: (1,2)
        :param node_path1: (3001,2002,3004)
        :param node_path2: (3001,2001,3004)
        :return:
        """
        assert node_path2 is not None

        dep = DepGraph()
        if node_path1==node_path2:
            dep.nodes = []
            return dep

        path1 = None
        if node_path1:
            path1 = [(node_path1[i],node_path1[i+1]) for i in range(len(node_path1)-1)]
        path2 = [(node_path2[i], node_path2[i + 1]) for i in range(len(node_path2) - 1)]

        if path1 == None:
            dep.nodes = [DepNode(Operation(
                node=link[0],
                type=Operation.ADD,
                pair=pair,
                dst=link[1]
            )) for link in path2]
            first = dep.nodes[0]
            first.op.path = node_path2
            for node in dep.nodes[1:]:
                node.acquire.append(first)
                first.release.append(node)
        else:
            op_map = {}
            path1_map = dict(path1)
            path2_map = dict(path2)
            for n,p in path2_map.items():
                if n in path1_map:
                    if p!=path1_map[n]:
                        op_map[n]= DepNode(Operation(
                            node=n,
                            type=Operation.MOD,
                            pair=pair,
                            dst=p
                        ))
                else:
                    op_map[n] = DepNode(Operation(
                        node=n,
                        type=Operation.ADD,
                        pair=pair,
                        dst=p
                    ))
            for n,p in path1_map.items():
                if n not in path2_map:
                    op_map[n]= DepNode(Operation(
                        node=n,
                        type=Operation.DEL,
                        pair=pair,
                        dst=p
                    ))
            firstmod = None
            for n,p in path2:
                if n not in op_map:
                    continue
                node = op_map[n]
                if node.op.type == Operation.MOD:
                    if firstmod is not None:
                        node.release.append(firstmod)
                        firstmod.acquire.append(node)
                    firstmod = node
                elif node.op.type == Operation.ADD:
                    if firstmod is not None:
                        node.release.append(firstmod)
                        firstmod.acquire.append(node)
                else:
                    raise Exception("unexpected operation")
            for n,p in path1:
                if n not in op_map:
                    continue
                node = op_map[n]
                if node.op.type == Operation.MOD:
                    firstmod = node
                elif node.op.type == Operation.DEL:
                    if firstmod is not None:
                        node.acquire.append(firstmod)
                        firstmod.release.append(node)
                else:
                    raise Exception("unexpected operation")
            dep.nodes = list(op_map.values())
            mod_node = [n for n in dep.nodes if n.op.type==Operation.MOD]
            assert len(mod_node)==1
            mod_node[0].op.path = node_path2
        return dep